package com.company.剑指offer每日刷题.普通版;

import java.util.List;

/**
 * 剑指 Offer 24. 反转链表
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL

 * 限制：
 * 0 <= 节点个数 <= 5000
 * */
public class ReverseList {
    /**
     * 方法：头插法
     * 思路： 我们新创建一个链表头newHead，以次遍历head的每一个节点，然后将这个新的节点作为newHead的头结点。
     *      这就有当前处理的节点的后继结点丢失的问题。所以当前节点在指向newHead头结点之前，保存当前节点的后继结点。下一次从这里继续向后操作。
     * */
    public ListNode reverseList(ListNode head) {
       ListNode newHead = null;
        while(head !=null){
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }
}
